Erreur de généralisation Ecart entre le Risque effectif et le Risque empirique. $$\hat R_l(\hat g_l)-R(\hat g_l)$$

Questions de cours

START
Ω Basique (+inversé optionnel)
Recto: Quelle quantité doit-on essayer de réduire au maximum pour diminuer l'erreur d'approximation ?
Verso: $$\sup_{g\in\mathcal S}R(g)-\hat R_l(g)$$
Bonus: $$R(\hat g_l)-R(g_*)\leqslant\underbrace{R(\hat g_l)-\hat R_l(\hat g_l)}_{\leqslant\sup_{g\in\mathcal S}R(g)-\hat R_l(g)}+\underbrace{\hat R_l(\hat g_l)-\hat R_l(g_*)}_{\leqslant0}+\underbrace{\hat R_l(g_*)-R(g_*)}_{\overset{\Bbb P}{\underset{l\to+\infty}\longrightarrow0}}$$
Carte inversée ?:
END
START
Ω Basique (+inversé optionnel)
Recto: De quoi dépend principalement cette quantité ? $${\Bbb E}\left[\sup_{g\in\mathcal S}R(g)-\hat R_l(g)\right]$$
Verso: De la richesse ou de la complexité de l'espace \(\mathcal S\).
Bonus:
Carte inversée ?:
END
START
Ω Basique (+inversé optionnel)
Recto: Donner une majoration de cette quantité lorsque \(\mathcal S\) est fini : $$\sup_{g\in\mathcal S}R(g)-\hat R_l(g)$$
Verso: On a avec probabilité \(1-\delta\) : $$\sup_{g\in\mathcal S}R(g)-\hat R_l(g)\leqslant\sqrt{\frac{\log(\lvert\mathcal S\rvert/\delta)}{2l}}\quad\text{ avec }\quad\delta:=\lvert\mathcal S\rvert e^{-2l\varepsilon^2}$$
Bonus: Cette majoration dépend du rapport entre le log du nombre d'élements dans la classe \(\ln(\lvert\mathcal S\rvert)\) et le nombre d'éléments de l'ensemble d'apprentissage \(l\).
(borne obtenue par Inégalité de Hoeffding)
Carte inversée ?:
END
START
Ω Basique (+inversé optionnel)
Recto: Peut-on utiliser la borne de l'Inégalité de Hoeffding lorsque \(\mathcal S\) est infini ? $$\sup_{g\in\mathcal S}R(g)-\hat R_l(g)\leqslant\sqrt{\frac{\log(\lvert\mathcal S\rvert/\delta)}{2l}}\quad\text{ avec }\quad\delta:=\lvert\mathcal S\rvert e^{-2l\varepsilon^2}$$
Verso: Ce n'est pas possible directement, mais on pourrait dire que, moralement, ce n'est pas le nombre d'éléments dans la classe qui compte mais le nombre d'éléments distincts "vu les données".
Bonus:
Carte inversée ?:
END